#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e5+10;
int a[maxn];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		long long n,k;
		int cnt = 0;
		scanf("%lld %lld",&n,&k);
		a[cnt++] = 1;
		a[cnt++] = n;
		for(int i = 2;i*i<=n;i++)
		{
			if(n%i==0)
			{
				a[cnt++] = i;
				a[cnt++] = n/i;
			} 
		}
		
		sort(a,a+cnt);
		long long ans = 0;
		for(int i = cnt-1;i>=0;i--)
		{
			//printf("**********\n");
			if(a[i]<=k)
			{
				ans = a[i];
				break;
			}
		}
		printf("%d\n",n/ans);
	}
} 
